home *** CD-ROM | disk | FTP | other *** search
/ PC World 2008 February (DVD) / PCWorld_2008-02_DVD.iso / v cisle / PHP / PHP.exe / xampp-win32-1.6.5-installer.exe / php / PEAR / FSM.php < prev    next >
Encoding:
PHP Script  |  2007-12-20  |  10.5 KB  |  313 lines
  1. <?php
  2. /* vim: set expandtab softtabstop=4 tabstop=4 shiftwidth=4: */
  3. /*
  4.  * Copyright (c) 2002-2006 Jon Parise <jon@php.net>
  5.  *
  6.  * Permission is hereby granted, free of charge, to any person obtaining a copy
  7.  * of this software and associated documentation files (the "Software"), to
  8.  * deal in the Software without restriction, including without limitation the
  9.  * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
  10.  * sell copies of the Software, and to permit persons to whom the Software is
  11.  * furnished to do so, subject to the following conditions:
  12.  *
  13.  * The above copyright notice and this permission notice shall be included in
  14.  * all copies or substantial portions of the Software.
  15.  *
  16.  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  17.  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  18.  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  19.  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  20.  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  21.  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
  22.  * IN THE SOFTWARE.
  23.  *
  24.  * $Id: FSM.php,v 1.15 2006/04/19 05:40:05 jon Exp $
  25.  */
  26.  
  27. /**
  28.  * This class implements a Finite State Machine (FSM).
  29.  *
  30.  * In addition to maintaining state, this FSM also maintains a user-defined
  31.  * payload, therefore effectively making the machine a Push-Down Automata
  32.  * (a finite state machine with memory).
  33.  *
  34.  * This code is based on Noah Spurrier's Finite State Machine (FSM) submission
  35.  * to the Python Cookbook:
  36.  *
  37.  *      http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/146262
  38.  *
  39.  * @author  Jon Parise <jon@php.net>
  40.  * @version $Revision: 1.15 $
  41.  * @package FSM
  42.  * @license http://www.opensource.org/licenses/mit-license.php MIT License
  43.  *
  44.  * @example rpn.php     A Reverse Polish Notation (RPN) calculator.
  45.  */
  46. class FSM
  47. {
  48.     /**
  49.      * Represents the initial state of the machine.
  50.      *
  51.      * @var string
  52.      * @see $_currentState
  53.      * @access private
  54.      */
  55.     var $_initialState = '';
  56.  
  57.     /**
  58.      * Contains the current state of the machine.
  59.      *
  60.      * @var string
  61.      * @see $_initialState
  62.      * @access private
  63.      */
  64.     var $_currentState = '';
  65.  
  66.     /**
  67.      * Contains the payload that will be passed to each action function.
  68.      *
  69.      * @var mixed
  70.      * @access private
  71.      */
  72.     var $_payload = null;
  73.  
  74.     /**
  75.      * Maps (inputSymbol, currentState) --> (action, nextState).
  76.      *
  77.      * @var array
  78.      * @see $_initialState, $_currentState
  79.      * @access private
  80.      */
  81.     var $_transitions = array();
  82.  
  83.     /**
  84.      * Maps (currentState) --> (action, nextState).
  85.      *
  86.      * @var array
  87.      * @see $_inputState, $_currentState
  88.      * @access private
  89.      */
  90.     var $_transitionsAny = array();
  91.  
  92.     /**
  93.      * Contains the default transition that is used if no more appropriate
  94.      * transition has been defined.
  95.      *
  96.      * @var array
  97.      * @access private
  98.      */
  99.     var $_defaultTransition = null;
  100.  
  101.  
  102.     /**
  103.      * This method constructs a new Finite State Machine (FSM) object.
  104.      *
  105.      * In addition to defining the machine's initial state, a "payload" may
  106.      * also be specified.  The payload represents a variable that will be
  107.      * passed along to each of the action functions.  If the FSM is being used
  108.      * for parsing, the payload is often a array that is used as a stack.
  109.      *
  110.      * @param   string  $initialState   The initial state of the FSM.
  111.      * @param   mixed   $payload        A payload that will be passed to each
  112.      *                                  action function.
  113.      */
  114.     function FSM($initialState, &$payload)
  115.     {
  116.         $this->_initialState = $initialState;
  117.         $this->_currentState = $initialState;
  118.         $this->_payload = &$payload;
  119.     }
  120.  
  121.     /**
  122.      * This method resets the FSM by setting the current state back to the
  123.      * initial state (set by the constructor).
  124.      */
  125.     function reset()
  126.     {
  127.         $this->_currentState = $this->_initialState;
  128.     }
  129.  
  130.     /**
  131.      * This method adds a new transition that associates:
  132.      *
  133.      *      (symbol, currentState) --> (nextState, action)
  134.      *
  135.      * The action may be set to NULL, in which case the processing routine
  136.      * will ignore the action and just set the next state.
  137.      *
  138.      * @param   string  $symbol         The input symbol.
  139.      * @param   string  $state          This transition's starting state.
  140.      * @param   string  $nextState      This transition's ending state.
  141.      * @param   string  $action         The name of the function to invoke
  142.      *                                  when this transition occurs.
  143.      *
  144.      * @see     addTransitions()
  145.      */
  146.     function addTransition($symbol, $state, $nextState, $action = null)
  147.     {
  148.         $this->_transitions["$symbol,$state"] = array($nextState, $action);
  149.     }
  150.  
  151.     /**
  152.      * This method adds the same transition for multiple different symbols.
  153.      *
  154.      * @param   array   $symbols        A list of input symbols.
  155.      * @param   string  $state          This transition's starting state.
  156.      * @param   string  $nextState      This transition's ending state.
  157.      * @param   string  $action         The name of the function to invoke
  158.      *                                  when this transition occurs.
  159.      *
  160.      * @see     addTransition()
  161.      */
  162.     function addTransitions($symbols, $state, $nextState, $action = null)
  163.     {
  164.         foreach ($symbols as $symbol) {
  165.             $this->addTransition($symbol, $state, $nextState, $action);
  166.         }
  167.     }
  168.  
  169.     /**
  170.      * This method adds an array of transitions.  Each transition is itself
  171.      * defined as an array of values which will be passed to addTransition()
  172.      * as parameters.
  173.      *
  174.      * @param   array   $transitions    An array of transitions.
  175.      *
  176.      * @see     addTransition
  177.      * @see     addTransitions
  178.      *
  179.      * @since 1.2.4
  180.      */
  181.     function addTransitionsArray($transitions)
  182.     {
  183.         foreach ($transitions as $transition) {
  184.             call_user_func_array(array($this, 'addTransition'), $transition);
  185.         }
  186.     }
  187.  
  188.     /**
  189.      * This method adds a new transition that associates:
  190.      *
  191.      *      (currentState) --> (nextState, action)
  192.      *
  193.      * The processing routine checks these associations if it cannot first
  194.      * find a match for (symbol, currentState).
  195.      *
  196.      * @param   string  $state          This transition's starting state.
  197.      * @param   string  $nextState      This transition's ending state.
  198.      * @param   string  $action         The name of the function to invoke
  199.      *                                  when this transition occurs.
  200.      *
  201.      * @see     addTransition()
  202.      */
  203.     function addTransitionAny($state, $nextState, $action = null)
  204.     {
  205.         $this->_transitionsAny[$state] = array($nextState, $action);
  206.     }
  207.  
  208.     /**
  209.      * This method sets the default transition.  This defines an action and
  210.      * next state that will be used if the processing routine cannot find a
  211.      * suitable match in either transition list.  This is useful for catching
  212.      * errors caused by undefined states.
  213.      *
  214.      * The default transition can be removed by setting $nextState to NULL.
  215.      *
  216.      * @param   string  $nextState      The transition's ending state.
  217.      * @param   string  $action         The name of the function to invoke
  218.      *                                  when this transition occurs.
  219.      */
  220.     function setDefaultTransition($nextState, $action)
  221.     {
  222.         if (is_null($nextState)) {
  223.             $this->_defaultTransition = null;
  224.             return;
  225.         }
  226.  
  227.         $this->_defaultTransition = array($nextState, $action);
  228.     }
  229.  
  230.     /**
  231.      * This method returns (nextState, action) given an input symbol and
  232.      * state.  The FSM is not modified in any way.  This method is rarely
  233.      * called directly (generally only for informational purposes).
  234.      *
  235.      * If the transition cannot be found in either of the transitions lists,
  236.      * the default transition will be returned.  Note that it is possible for
  237.      * the default transition to be set to NULL.
  238.      *
  239.      * @param   string  $symbol         The input symbol.
  240.      *
  241.      * @return  mixed   Array representing (nextState, action), or NULL if the
  242.      *                  transition could not be found and not default
  243.      *                  transition has been defined.
  244.      */
  245.     function getTransition($symbol)
  246.     {
  247.         $state = $this->_currentState;
  248.  
  249.         if (!empty($this->_transitions["$symbol,$state"])) {
  250.             return $this->_transitions["$symbol,$state"];
  251.         } elseif (!empty($this->_transitionsAny[$state])) {
  252.             return $this->_transitionsAny[$state];
  253.         } else {
  254.             return $this->_defaultTransition;
  255.         }
  256.     }
  257.  
  258.     /**
  259.      * This method is the main processing routine.  It causes the FSM to
  260.      * change states and execute actions.
  261.      *
  262.      * The transition is determined by calling getTransition() with the
  263.      * provided symbol and the current state.  If no valid transition is found,
  264.      * process() returns immediately.
  265.      *
  266.      * The action callback may return the name of a new state.  If one is
  267.      * returned, the current state will be updated to the new value.
  268.      *
  269.      * If no action is defined for the transition, only the state will be
  270.      * changed.
  271.      *
  272.      * @param   string  $symbol         The input symbol.
  273.      *
  274.      * @see     processList()
  275.      */
  276.     function process($symbol)
  277.     {
  278.         $transition = $this->getTransition($symbol);
  279.  
  280.         /* If a valid array wasn't returned, return immediately. */
  281.         if (!is_array($transition) || (count($transition) != 2)) {
  282.             return;
  283.         }
  284.  
  285.         /* Update the current state to this transition's exit state. */
  286.         $this->_currentState = $transition[0];
  287.  
  288.         /* If an action for this transition has been specified, execute it. */
  289.         if (!empty($transition[1])) {
  290.             $state = call_user_func_array($transition[1],
  291.                                           array($symbol, &$this->_payload));
  292.  
  293.             /* If a new state was returned, update the current state. */
  294.             if (!empty($state) && is_string($state)) {
  295.                 $this->_currentState = $state;
  296.             }
  297.         }
  298.     }
  299.  
  300.     /**
  301.      * This method processes a list of symbols.  Each symbol in the list is
  302.      * sent to process().
  303.      *
  304.      * @param   array   $symbols        List of input symbols to process.
  305.      */
  306.     function processList($symbols)
  307.     {
  308.         foreach ($symbols as $symbol) {
  309.             $this->process($symbol);
  310.         }
  311.     }
  312. }
  313.